package server.simple100;

import org.junit.Test;

/***
 *  111. 二叉树的最小深度
 */
public class LeetCode111 {


	@Test
	public void test() {
		//   [2,null,3,null,4,null,5,null,6]
		//               2
		//         null      3
		//               null   4
		//                      null 5
		//                        null   6
		//

//		TreeNode root = new TreeNode(0,
//				new TreeNode(2, new TreeNode(1, new TreeNode(5), new TreeNode(1)), null),
//				//new TreeNode(2),
//				new TreeNode(4, new TreeNode(3, null, new TreeNode(6)), new TreeNode(-1, null, new TreeNode(8))
//				));

		TreeNode root = new TreeNode(2,
				null, new TreeNode(3,
				null, new TreeNode(4,
				null, new TreeNode(5,
				null, new TreeNode(6
		)))
		));
		System.out.println(minDepth(root));
	}


	public int minDepth(TreeNode root) {
		if (root != null) {
			int leftNum = minDepth(root.left);
			int rightNum = minDepth(root.right);
			if (root.left == null && root.right == null) {
				// 情况1  左右节点都为 null
				return 1;
			} else if (root.left == null || root.right == null) {
				// 情况2  左右节点有一个为 null (取大的值返回)
				int num = leftNum > rightNum ? leftNum : rightNum;
				return num + 1;
			} else {
				// 情况3  左右都不为 null
				int num = leftNum < rightNum ? leftNum : rightNum;
				return num + 1;
			}
		} else {
			return 0;
		}
	}


	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}

//给定一个二叉树，找出其最小深度。
//
//		最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
//
//		说明：叶子节点是指没有子节点的节点。
//
//		 
//
//		示例 1：
//
//
//		输入：root = [3,9,20,null,null,15,7]
//		输出：2
//		示例 2：
//
//		输入：root = [2,null,3,null,4,null,5,null,6]
//		输出：5
//		 
//
//		提示：
//
//		来源：力扣（LeetCode）
//		链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
//		著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。